// 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

// 示例1：

// 输入：1->2->4, 1->3->4
// 输出：1->1->2->3->4->4

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// 遍历

// 执行用时：
// 24 ms
// , 在所有 C++ 提交中击败了
// 68.13%
// 的用户
// 内存消耗：
// 19.1 MB
// , 在所有 C++ 提交中击败了
// 9.35%
// 的用户


  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
 
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* res = l1;
        ListNode* l1_pre = l1;
        if(l1==NULL){
            return l2;
        }
        while(true){
            if(l1==NULL){
                if(l2!=NULL){
                    ListNode* temp = new ListNode(l2->val);
                    temp->next = l2->next;
                    l1_pre->next= temp;
                }
                l1 = l2;
                break;
            }
            else if(l2==NULL){
                break;
            }
            else{
                if(l1->val<l2->val){
                    l1_pre = l1;
                    l1=l1->next;
                }
                else{
                    ListNode* temp = new ListNode(l1->val);
                    l1->val = l2->val;
                    ListNode* l1_next=l1->next;
                    l1->next=temp;
                    temp->next=l1_next;
                    l1_pre = l1;
                    l1= l1->next;
                    l2=l2->next;
                }

            }
        }
        return res;
    }
};